package com.xxwy.lintcode;

/**
 * @author xxwy
 * on 2018/10/8 0008
 * Jump Game： 存在性
 * 给出一个非负整数数组，你最初定位在数组的第一个位置。　　　
 *
 * 数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　　
 *
 * 判断你是否能到达数组的最后一个位置。
 * --------------------------------
 * 这个问题有两个方法，一个是贪心和 动态规划。
 *
 * 贪心方法时间复杂度为O（N）。
 *
 * 动态规划方法的时间复杂度为为O（n^2）
 * ---------------------
 * 例子：
 * A = [2,3,1,1,4]，返回 true.
 *
 * A = [3,2,1,0,4]，返回 false.
 *
 */
public class Num116 {

    public boolean canJump(int[] A) {
        // write your code here
        if(A == null ||A.length == 0){
            return false;
        }
        int n = A.length;
        boolean[] f = new boolean[n];
        f[0] = true;
        for (int i = 1; i < n; i++) {
            f[i] = false;
            for (int j = 0; j < i; j++) {
                if(f[j] && j + A[j] >= i){
                    f[i] = true;
                    break;
                }

            }
        }
        return f[n-1];
    }
}
